package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 有理函数类（帕德逼近结果）
class Rational {
    private final List<Double> numerator;   // 分子多项式系数（逆序存储）
    private final List<Double> denominator; // 分母多项式系数（逆序存储）

    // 构造函数：a=分子系数，b=分母系数（原始顺序，内部逆序存储）
    public Rational(List<Double> a, List<Double> b) {
        this.numerator = new ArrayList<>(a);
        Collections.reverse(this.numerator);
        this.denominator = new ArrayList<>(b);
        Collections.reverse(this.denominator);
    }

    // 计算有理函数在x处的值
    public double apply(double x) {
        double numVal = calcPolynomial(numerator, x);
        double denVal = calcPolynomial(denominator, x);
        if (Math.abs(denVal) < 1e-15) {
            throw new ArithmeticException("分母为0，无法计算");
        }
        return numVal / denVal;
    }

    // 多项式字符串表示
    @Override
    public String toString() {
        String numStr = polyToString(numerator);
        String denStr = polyToString(denominator);
        return "(" + numStr + ")/(" + denStr + ")";
    }

    // 辅助方法：计算多项式值（霍纳法则）
    private double calcPolynomial(List<Double> coefficients, double x) {
        double result = 0.0;
        for (double coeff : coefficients) {
            result = result * x + coeff;
        }
        return result;
    }

    // 辅助方法：多项式转字符串
    private String polyToString(List<Double> coefficients) {
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        int n = coefficients.size();
        for (int i = 0; i < n; i++) {
            double coeff = coefficients.get(i);
            if (Math.abs(coeff) < 1e-15) { // 忽略0系数
                continue;
            }
            // 处理符号
            if (!first) {
                sb.append(coeff > 0 ? "+" : "");
            } else {
                first = false;
            }
            // 处理系数
            if (Math.abs(coeff) != 1.0 || (n - i - 1) == 0) { // 系数不为1 或 常数项
                sb.append(coeff);
                if ((n - i - 1) > 0) {
                    sb.append("*");
                }
            }
            // 处理x的幂次
            int order = n - i - 1;
            if (order > 0) {
                sb.append("x");
                if (order > 1) {
                    sb.append("**").append(order);
                }
            } else if (Math.abs(coeff) == 1.0) { // 常数项1
                sb.append("1");
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

// 帕德逼近工具类
public class PadeApproximation {

    // 帕德逼近核心方法
    // coefficients: 泰勒展开系数数组
    // m: 分子多项式阶数
    // n: 分母多项式阶数
    public static Rational pade(List<Double> coefficients, int m, int n) {
        // 第一步：构建线性方程组矩阵，求解分母系数b
        List<List<Double>> lines = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int start = i + 1;
            int end = i + n + 1;
            List<Double> line = new ArrayList<>();
            // 截取并逆序系数
            for (int j = start; j < end && j < coefficients.size(); j++) {
                line.add(coefficients.get(j));
            }
            // 补0（如果系数不足）
            while (line.size() < n) {
                line.add(0.0);
            }
            Collections.reverse(line);
            lines.add(line);
        }
        Matrix matrix = new Matrix(lines);

        // 构建右侧值数组（取反）
        List<Double> values = new ArrayList<>();
        for (int i = m + 1; i <= m + n && i < coefficients.size(); i++) {
            values.add(-coefficients.get(i));
        }
        // 补0（如果值不足）
        while (values.size() < n) {
            values.add(0.0);
        }

        // 求解分母系数b
        List<Double> b = matrix.solveByLup(values);
        b.add(0, 1.0); // b0 = 1

        // 第二步：计算分子系数a
        List<Double> a = new ArrayList<>();
        for (int i = 0; i <= m; i++) {
            double a_i = 0.0;
            for (int j = 0; j <= i; j++) {
                if (j < coefficients.size() && (i - j) < b.size()) {
                    a_i += coefficients.get(j) * b.get(i - j);
                }
            }
            a.add(a_i);
        }

        // 返回有理函数
        return new Rational(a, b);
    }

    // 测试示例
    public static void main(String[] args) {
        // 示例：e^x的泰勒展开前几项系数 [1, 1, 0.5, 1/6, 1/24, 1/120]
        List<Double> coefficients = new ArrayList<>();
        coefficients.add(1.0);
        coefficients.add(1.0);
        coefficients.add(0.5);
        coefficients.add(1.0 / 6);
        coefficients.add(1.0 / 24);
        coefficients.add(1.0 / 120);

        // 计算Pade(2,2)逼近
        Rational pade = PadeApproximation.pade(coefficients, 2, 2);
        System.out.println("帕德逼近有理函数：" + pade);
        System.out.println("在x=1处的值：" + pade.apply(1.0));
        System.out.println("e^1的真实值：" + Math.exp(1.0));
    }
}